package com.fr.lintcode;

/**
*作者：furong
*日期：2017年3月7日
*时间：上午11:28:01
*/
public class Q202 {
    /**
     *@param root, start, end: The root of segment tree and 
     *                         an segment / interval
     *@return: The maximum number in the interval [start, end]
     */
    public int query(SegmentTreeNode root, int start, int end) {
        if (root == null) {
            return 0;
        }
        if (root.start == start && root.end == end) {
            return root.max;
        }
        int mid = (root.start + root.end) / 2;
        if (mid < start) {
            return query(root.right, start, end);
        } else if (mid >= end) {
            return query(root.left, start, end);
        }
        int left = query(root.left, start, mid);
        int right = query(root.right, mid + 1, end);
        return Math.max(left, right);
    }
}
